package com.darrenchan.leetcode;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2020-02-28 19:44
 */
public class QLint200 {

    public String longestPalindrome(String s) {
        if(s == null || s.length() == 0) {
            return s;
        }

        int len = s.length();
        int max = 0, start = 0;
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        for (int i = 0; i < len - 1; i++) {
            if(s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
                max = 2;
                start = i;
            }
        }

        for (int i = len - 1; i >= 0; i--) {
            for (int j = i + 2; j < len; j++) {
                dp[i][j] = dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
                if(dp[i][j]) {
                    if(max < j - i + 1) {
                        max = j - i + 1;
                        start = i;
                    }
                }
            }
        }

        return s.substring(start, start + max);
    }
}
